package com.leetcode.partition11;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/12/7 12:13
 */
public class LC1034边界着色 {

    private static final int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    public static int[][] colorBorder(int[][] grid, int row, int col, int color) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        dfs(grid, row, col, color, visited);
        return grid;
    }

    public static void main(String[] args) {
        int[][] grid = {
                {1, 2, 1, 2, 1, 2},
                {2, 2, 2, 2, 1, 2},
                {1, 2, 2, 2, 1, 2}
        };
        int row = 1, col = 3, color = 1;
        colorBorder(grid, row, col, color);
        Arrays.stream(grid).forEach(val -> System.out.println(Arrays.toString(val)));
    }

    private static void dfs(int[][] grid, int row, int col, int color, boolean[][] visited) {
        visited[row][col] = true;
        boolean isBorder = false;
        //检查当前位置是否是连通边界，最边界上的一定是连通边界
        if (row == 0 || row == grid.length - 1 || col == 0 || col == grid[0].length - 1) isBorder = true;
        if (!isBorder) {
            //如果不是最边上，需要检查当前位置的四周，如果四周有任何一个其它颜色的格子，当前格子也是连通边界
            for (int[] dir : dirs) {
                int x = row + dir[0], y = col + dir[1];
                if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != grid[row][col]) {
                    isBorder = true;
                    break;
                }
            }
        }
        //先进行递归回溯再进行染色，避免判断边界出错
        for (int[] dir : dirs) {
            int x = row + dir[0], y = col + dir[1];
            if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != grid[row][col] || visited[x][y]) continue;
            dfs(grid, x, y, color, visited);
        }
        //如果当前位置是连通边界，进行染色
        if (isBorder) grid[row][col] = color;
    }
}
